package LeetCode_力扣;
//92. 反转链表 II (翻转局部链表)

/**
 * 思路一：还是要头插法，只不过不是全部节点进行头插，而是 left ~ right 之间
 * 进行头插。
 * 用prve 和 node指针，node每次都像后移动，prve只有不需要头插节点才向后移动
 * 再用指针 tt 保存第一个头插节点，因为后面需要更新他的执行地址
 */

/*

public class reverseBetween_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {

        if(head == null || head.next == null){
            return head;
        }

        ListNode dummyHead = new ListNode();//虚拟头节点
        dummyHead.next = head;//连接一下
        ListNode prve = dummyHead;//不需要头插的节点才往下走
        ListNode node = prve.next;//每次都往下走

        ListNode tt = node;
        for (int i = 1; node != null ; i++) {

            if(i >= left && i <= right){

                //说明此时的链表需要头插
                ListNode cur = new ListNode(node.val);//新节点,下一个节点的值

                if(i == left){
                    //保存第一个头插的节点
                    tt = cur;
                }

                cur.next = prve.next;
                prve.next = cur;

                if(i == right){
                    //更新头插的第一个节点指向地址
                    //为第一个不需要头插的节点地址
                    tt.next = node.next;
                }

            }else {
                //不需要头插的节点才往下走
                prve = prve.next;
            }
            //每次都往下走
            node = node.next;
        }
        return dummyHead.next;


    }
}

 */


/**
 * 思路二：使用三指针迭代法. prve - cur - next
 * 需要保存第一次翻转的 prve 和 cur
 * 需要保存不再翻转时的 prve 和 cur
 * 需要分两种情况，一是头节点不需要翻转，二是头节点需要翻转
 */
//注释：还需要考虑是从第一个开始翻转的话就不能return head 了

/*

public class reverseBetween_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {

        if(head == null || head.next == null){
            return head;
        }
        //此时说明至少有两个节点
        ListNode prve = head;
        ListNode cur = head;
        //需要保存四个节点的地址
        ListNode p1 = prve, p2 = prve;
        ListNode c1 = cur, c2 = cur;

        for (int i = 1; cur != null ; i++) {

            ListNode next = cur.next;

            if(i >= left && i <= right){

                if(i == left){
                    p1 = prve;
                    c1 = cur;
                }

                cur.next = prve;

            }

            prve = cur;
            cur  = next;

            if(i == right){
                p2 = prve;
                c2 = cur;
            }

        }

        p1.next = p2;
        c1.next = c2;


        if(c1 == head){
            //说明此刻是从第一个节点就可以翻转了
            return p2;
        }

        return head;

    }
}

*/

//上面两个方法写的太浪费了，这里写个结合的。
/**
 * 迭代法：三指针 + 头插。因为第一个节点可能也是带反转节点
 * 所以为了方便头插，弄一个虚拟头节点来进行。
 * 让prve指针循环 left - 1，成为 前驱。保持不动。
 * 然后创建 cut 和 next指针，让 cut执行 next.next
 * 就是跳过待头插的节点。next在待头插节点的位置。进行头插
 * 循环 right - left 次。
 */

/*

public class reverseBetween_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {

        //判空
        if(head == null || head.next == null){
            return head;
        }

        ListNode dummyHead = new ListNode();//创建虚拟头节点
        dummyHead.next = head;//连接一下
        ListNode prve = dummyHead;//前驱

        for (int i = 0; i < left - 1; i++) {
             prve = prve.next;
        }//找到前驱的位置

        //创建三指针
        ListNode cur = prve.next;
        ListNode next = cur.next;

        //注释：cur位置和prve是不能动的
        for (int i = 0; i < right - left; i++) {
            cur.next = next.next;//跳过一个节点

            next.next = prve.next;
            prve.next = next;

            next = cur.next;//更新next的位置
        }

        return dummyHead.next;
    }
}

 */



/**
 * 递归实现
 */

/**
 * 思路三： 定义一个静态变量，让它执行翻转后末尾节点指向的地址，保留。
 * 末尾的节点分为两种情况，第一种是 后面不存在不需要翻转的节点，那么此刻的 next就应该是null
 * 第二种是 后面存在 不需要翻转的节点，如：1~5 我只翻转 2到4，那么 5 就是不需要翻转的节点，
 * 那么此刻的 next 保存的就是 5 的地址，这种情况发生在 left == right 时刻发生。
 */


/*

public class reverseBetween_92 {
    //定义一个静态变量，让它执行翻转后末尾节点指向的地址，保留。
    public static ListNode next = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {

        //终止条件
        if( head.next == null || left == right ){
            next = head.next;
            return head;
        }

        //情况一 left == 1 从头就开始反转
        if(left == 1){
            //我们从处理头的反转
            ListNode prve = head;
            ListNode cur = head.next;//等会反转后末尾节点地址
            ListNode node = reverseBetween(head.next, left, right - 1);
            cur.next = prve;
            prve.next = next;

            return node;
        }

        //情况二，前面有节点不需要翻转

        ListNode prve = head;

        prve.next = reverseBetween(head.next, left -1, right - 1);
        return prve;
    }
}

 */






/*

public class reverseBetween_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {

    }
}

*/


//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode() {
//    }
//
//    ListNode(int val) {
//        this.val = val;
//    }
//
//    ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//}
